package com.suanfa.jiaoheng;

import java.util.Arrays;

/**
 * 分而治之的思想之快速排序
 * 也是递归思想的一种体现
 *
 * 重要的是找出问题的基线条件+缩小问题规模
 *
 * 数组的基线条件基本都是数组为空或只包含一个元素
 *
 * 感觉快排是递归实现的一个升级，先递归分组，再递归排序
 */
public class 第4课快速排序 {
    public static void main(String[] args) {
        int[] numArr = new int[]{7,4,2,6,5,3,8,1};
        quickSort(numArr,0,numArr.length-1);
        Arrays.stream(numArr).forEach(value -> System.out.print(value+" "));
    }

    // 快速排序
    public static void quickSort(int[] numArr,int startPos,int endPos){
        // 拆分过程，是个递归过程
        if(endPos-startPos<=0){
            //如果数组少于两个则不拆分(这是基线条件)，这样使用卫语句写更清楚点
            return;
        }else{
            int splitPos = (startPos+endPos)/2;
            quickSort(numArr,startPos,splitPos);
            quickSort(numArr,splitPos+1,endPos); // 注意这里的splitPos+1的操作
            // 组合排序过程，组合排序startPos,splitPos这段数组和splitPos,endPos这段数组
            sort2Array(numArr,startPos,splitPos,endPos);
        }

    }
    /**
     * 排序两段数组
     * 从两个排好序的数组中分别取值判断，放到新数组，再放到原数组
     */
    public static void sort2Array(int[] numArr,int startPos,int splitPos,int endPos){
        // 创建个临时数组保存排好序的数据
        int[] tempSortArr = new int[endPos-startPos+1];
        // 分别定义指向两个数组中的还未比较和处理的数字位置
        int leftPointPos = startPos;
        int rightPointPos = splitPos+1;
        for(int tempSortArrPos = 0;tempSortArrPos<tempSortArr.length;tempSortArrPos++){

            if(leftPointPos>splitPos){
                // 这里是处理左数组已经处理完的情况
                tempSortArr[tempSortArrPos] = numArr[rightPointPos];
                rightPointPos++;
                continue;
            }
            if(rightPointPos>endPos){
                // 处理右数组已经处理完成的情况
                tempSortArr[tempSortArrPos] = numArr[leftPointPos];
                leftPointPos++;
                continue;
            }
            // 从左右数组中寻找较小的数
            if(numArr[leftPointPos]<=numArr[rightPointPos]){
                tempSortArr[tempSortArrPos] = numArr[leftPointPos];
                leftPointPos++;
            } else{
                tempSortArr[tempSortArrPos] = numArr[rightPointPos];
                rightPointPos++;
            }
        }
        for(int numArrPos = startPos,tempSortArrPos = 0;numArrPos<=endPos;numArrPos++,tempSortArrPos++){
            numArr[numArrPos] = tempSortArr[tempSortArrPos];
        }
    }
}
